#include <iostream>
#include <vector>
using namespace std;
// 什么是二叉搜索树？
// 二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，满足以下性质：
// 左子树的所有节点的值都小于该节点的值，
// 其右子树中的所有节点的值都大于该节点的值。
// 特性：中序遍历结果是单调递增的有序序列
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 思路： 递归， 每次选择中间节点作为根节点
// 具体思路：每一次选择中间节点作为根节点，左边的子数组作为左子树，右边的子数组作为右子树，递归构建
class Solution
{
public:
    TreeNode *sortedArrayToBST(vector<int> &nums)
    {
        return build(nums, 0, nums.size() - 1);
    }
    TreeNode *build(vector<int> &nums, int left, int right)
    {
        if (left > right) // 递归终止条件
            return nullptr;
        int mid = (left + right) / 2;              // 选择中间节点作为根节点
        TreeNode *root = new TreeNode(nums[mid]);  // 创建根节点
        root->left = build(nums, left, mid - 1);   // 递归构建左子树
        root->right = build(nums, mid + 1, right); // 递归构建右子树
        return root;
    }
};